import java.util.ArrayList;
import java.util.List;
import java.util.Stack;



public class Solution {
    public int[][] threeOrders (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        int[][] ans = new int[3][];
        preOrder(root, list);
        ans[0] = getArray(list);
        list = new ArrayList<>();
        inOrder(root, list);
        ans[1] = getArray(list);
        list = new ArrayList<>();
        postOrder(root, list);
        ans[2] = getArray(list);
        return ans;
    }
    public int[] getArray(List<Integer> list) {
        int len = list.size();
        int[] array = new int[len];
        for (int i = 0; i < len; i++) {
            array[i] = list.get(i);
        }
        return array;
    }



    /*递归*/
    public void preOrder(TreeNode root, List<Integer> list) {
        if (root != null) {
            list.add(root.val);
            preOrder(root.left, list);
            preOrder(root.right, list);
        }
    }
    public void inOrder(TreeNode root, List<Integer> list) {
        if (root != null) {
            inOrder(root.left, list);
            list.add(root.val);
            inOrder(root.right, list);
        }
    }
    public void postOrder(TreeNode root, List<Integer> list) {
        if (root != null) {
            postOrder(root.left, list);
            postOrder(root.right, list);
            list.add(root.val);
        }
    }



}
class Solution2{
    /*迭代*/
    public void preOrder(TreeNode root, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                list.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop().right;
            }
        }
    }
    public void inOrder(TreeNode root, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop();
                list.add(curr.val);
                curr = curr.right;
            }
        }
    }
    public void postOrder(TreeNode root, List<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                list.add(0, curr.val);
                curr = curr.right;
            } else {
                curr = stack.pop();
                curr = curr.left;
            }
        }
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
